﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
// 原题连接：https://leetcode.cn/problems/majority-element/
// 题目描述：
/*
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3

示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
*/

// 方法1——暴力法(但会超出时间)
/*
思路：
对于每个元素都向它的后面遍历，
找到与它相同的元素，用一个变量count保存，
若相同的元素个数超过⌊ n/2 ⌋则直接返回
因为是要找出现次数大于⌊ n/2 ⌋，
故第一层循环只需⌊ n/2 ⌋次。
*/
int majorityElement1(int* nums, int numsSize) {
	assert(nums);
	int N = numsSize / 2; 
	int i = 0;
	int j = 0;
	for (i = 0; i < N; i++) {
		int count = 1;
		for (j = i + 1; j < numsSize; j++) {
			if (nums[j] == nums[i]) {
				count++;
			}
		}
		if (count > N) {
			break;
		}
	}
	return nums[i];
}

// 方法2——排序
/*
思路：
如果将数组nums中的所有元素按单调递增或递减的顺序排序，那么下标为⌊ n/2 ⌋的元素
一定就是众数。
*/
int majorityElement2(int* nums, int numsSize) {
	assert(nums);
	// 先对数组进行排序
	int i = 0;
	int j = 0;
	for (i = 0; i < numsSize - 1; i++) {
		int flag = 1;
		for (j = 0; j < numsSize - 1 - i; j++) {
			if (nums[j] > nums[j + 1]) {
				int temp = nums[j];
				nums[j] = nums[j + 1];
				nums[j + 1] = temp;
				flag = 0;
			}
		}
		if (flag) {
			break;
		}
	}
	return nums[numsSize / 2];
}

// 方法3——一对一打擂台
/*
思路：
我们可以根据数组中的元素的不同数值八元素分成若干个队
(即数值相同的元素为一队)
假设有一个擂台，一次只能上一个人，如果上来的人与台上的人是同一队的
则可以留下来，若不是一对的就将台上的人抵消掉一个,即一人对一人，
并且都同归于尽。
这样，到最后留在台上的人一定是，人数最多的那一队中的人。
我们先给一个"令牌"给第一个上台的人，如果后面上来那个人是自己队的，
则两个人都能留下，即令牌守住。若后面上来的那个人不是自己队的，
这两个人同归于尽，令牌要传给下一个上台的人。
就这样，最后哪一队的人手上有令牌就是那一队胜出。
*/

int majorityElement3(int* nums, int numsSize) {
	int index = nums[0]; // 先把令牌给第一个上台的人
	int i = 0;
	int count = 0; // 统计台上的一共有多少个某队的人
	for (i = 0; i < numsSize; i++) {
		if (nums[i] == index) {
			count++;
		}
		else {
			count--;
			if (count == 0) {
				index = nums[i + 1];
			}
		}
	}
	return index;
}


int main() {
	int arr[] = { 2,2,1,1,1,2,2 };
	int len = sizeof(arr) / sizeof(arr[0]);
	printf("%d", majorityElement3(arr, len));

	return 0;
}